Previous | Index | Next |

Sequences

A sequence is a kind of container that organizes a finite set of objects, all of the same type, into a strictly linear arrangement. The library provides four basic kinds of sequence containers: Vector, List, SingleList and Deque. It also provides container adaptors that make it easy to construct abstract data types, such as stacks or queues, out of the basic sequence kinds (or out of other kinds of sequences that the user might define).

In the following two tables, X is a sequence class, a is value of X, i and j satisfy input iterator requirements, [i,j) is a valid range, n is a int, p is a valid iterator to a, q is a dereferenceable iterator to a, [q1,q2) is a valid range in a, t is a value of Object.

The complexities of the expressions are sequence dependent.

The sequence requirements are defined in the SequenceContainer api interface.

Sequence requirements (in addition to container)
expression return type assertion/note
pre/post-condition
X(n, t); . post: size() == n.
constructs a sequence with n copies of t.
X(i, j) . post: size() == distance between i and j.
constructs a sequence equal to the range [i,j).
a.insert(p, t) Iterator inserts a copy of t before p.
the return value points to the inserted copy.
a.insert(p, n, t) void inserts n copies of t before p.
a.insert(p, i, j) void inserts copies of elements in [i,j) before p.
a.erase(q) void erases the element pointed to by q.
a.erase(q1, q2) void erases the elements in the range [q1,q2) .

Vector, List, and Deque offer the programmer different complexity trade-offs and should be used accordingly. Vector is the type of sequence that should be used by default. List should be used when there are frequent insertions and deletions from the middle of the sequence. Deque is the data structure of choice when most insertions and deletions take place at the beginning or at the end of the sequence.

Iterator types for sequences have to be at least of the forward iterator category.

All the operations in the tables below are provided only for the containers for which they take constant time.

Optional sequence operations
expression return type operational semantics container
a.front() Object; a.beginRef().get() Vector, List,Deque
a.back() Object; a.end().prev().get() Vector, List,Deque
a.get(n) Object a.begin().next(n).get() Vector, Deque
a.put(x, n) Object a.begin().next(n).put(x) Vector, Deque

The front insert requirements are defined in the FrontInsertContainer api interface.

Front insert operations
expression return type operational semantics container
a.push_front(t) void a.insert(a.begin(), t) List, Deque
a.pop_front() void a.erase(a.begin()) List, Deque

The back insert requirements are defined in the BackInsertContainer api interface.

Back insert operations
expression return type operational semantics container
a.push_back(t) void a.insert(a.end(), t) Vector, List, Deque
a.pop_back() void a.erase(a.endCopy().prev()) Vector, List, Deque


Previous | Index | Next |